home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph_alg / _all_pairs.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  2.0 KB  |  75 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _all_pairs.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  ALL PAIRS SHORTEST PATHS                                                    *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23. #include <LEDA/graph_alg.h>
  24.  
  25. bool ALL_PAIRS_SHORTEST_PATHS(graph&G, const edge_array<num_type>& cost, 
  26.                                              node_matrix<num_type>& DIST)
  27. { 
  28.   // computes for every node pair (v,w) DIST(v,w) = cost of the least cost
  29.   // path from v to w, the single source shortest paths algorithms BELLMAN_FORD
  30.   // and DIJKSTRA are used as subroutines. Returns false if there is a
  31.   // negative cost circle and true otherwise.
  32.  
  33.   edge e;
  34.   node v,w;
  35.  
  36.   num_type C = 0;
  37.   forall_edges(e,G)  C += ((cost[e]>0) ? cost[e] : -cost[e]);
  38.  
  39.   node s = G.new_node();
  40.   forall_nodes(v,G) G.new_edge(s,v);
  41.  
  42.   edge_array<num_type> cost1(G);
  43.   node_array<num_type> dist1(G);
  44.  
  45.   node_array<edge>  pred(G);
  46.  
  47.   forall_edges(e,G)  
  48.     if (source(e)==s) cost1[e] = C;
  49.     else cost1[e] =  cost[e];
  50.  
  51.   if (!BELLMAN_FORD(G,s,cost1,dist1,pred)) return false;
  52.  
  53.   G.del_node(s);
  54.  
  55.   forall_edges(e,G) cost1[e] = dist1[source(e)] + cost[e] - dist1[target(e)];
  56.  
  57.  
  58.   // (G,cost1) is a non-negative network
  59.   // for every node v compute row DIST[v] of the distance matrix  DIST 
  60.   // by a call of DIJKSTRA(G,v,cost1,DIST[v])
  61.  
  62.   forall_nodes(v,G) DIJKSTRA(G,v,cost1,DIST[v],pred);
  63.  
  64.  
  65.   // correct the entries of DIST
  66.  
  67.   forall_nodes(v,G)
  68.   { num_type dv = dist1[v];
  69.     forall_nodes(w,G) DIST(v,w) += (dist1[w] - dv);
  70.    }
  71.  
  72.  return true;
  73. }
  74.  
  75.